package 极客算法训练营.chapter06;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class N叉树的后序遍历 {
    class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }

    class Solution1 {
        public List<Integer> postorder(Node root) {
            List<Integer> res = new ArrayList<>();
            recursionTree(root, res);
            return res;
        }

        public void recursionTree(Node root, List<Integer> res) {
            if (root == null) return;
            for (Node node : root.children) {
                recursionTree(node, res);
            }
            res.add(root.val);
        }
    }

    class Solution2 {
        public List<Integer> postorder(Node root) {
            LinkedList<Integer> res = new LinkedList<>();
            Deque<Node> stack = new LinkedList<>();
            if (root == null) return res;
            stack.push(root);
            while (!stack.isEmpty()) {
                Node pop = stack.pop();
                res.addFirst(pop.val);
                if (pop.children != null) {
                    for (Node child : pop.children) {
                        stack.push(child);
                    }
                }
            }
            return res;
        }
    }

}
